package Top_Interview_Questions.Sort;

import java.util.*;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/21 19:43
 * <p>
 * 功能描述:
 */
public class _0350 {


/*---------------------------------------排序---------------------------------------*/

    /**
     * https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution
     * /liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode/
     *
     * 打败%99的人
     *
     * 1.i是nums1的指针，所以这里i和j不能调换顺序。如果调换了,下面这个例子就会报错。
     * [1,2,2,1]
     * [2,2]
     *
     * 输出
     * [1,1]
     * 预期结果
     * [2,2]
     *
     * #.nums2[k++] = nums2[j++];
     *   i++;
     *   return Arrays.copyOfRange(nums2, 0, k) 这样子换是可以的
     */
    public int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                ++i;
            } else if (nums1[i] > nums2[j]) {
                ++j;
            } else {
                nums1[k++] = nums1[i++]; //1.
                ++j;
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);

    }

/*------------------------------------------------------------------------------------*/



/*---------------------------------------哈希映射---------------------------------------*/

    /**
     * https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution
     * /liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode/
     *
     * 打败%78的人
     */
    public int[] intersect1(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect1(nums2, nums1);
        }
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int n : nums1) {
            m.put(n, m.getOrDefault(n, 0) + 1);
        }
        int k = 0;
        for (int n : nums2) {
            int cnt = m.getOrDefault(n, 0);
            if (cnt > 0) {
                nums1[k++] = n;
                m.put(n, cnt - 1);
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);

    }

/*------------------------------------------------------------------------------------*/
}
